package seqlist;

import java.nio.file.ProviderNotFoundException;

// 车厢类
class Node {

    // 存储具体元素
    int data;
    // 存储下一个结点地址(钩子)
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}


// 火车
public class SingleLinkedList {

    // 当前火车中车厢的个数(实际存储的元素个数)
    private int size;
    // 当前火车的第一个结点
    private Node head;
    // 在火车头部添加元素
    public void addFirst(int data) {
        // 要使用addFirst向火车中添加结点，要判断当前火车是否为空
        // -> 一个结点都没有
        // 要插入的结点就是第一个结点
        if(size == 0) {
            Node node = new Node(data);
            head = node;
            size ++;
        }else {
            // 当前火车已经存在结点了
            Node node = new Node(data);
            node.next = head;
            head = node;
            size ++;
        }
    }

    public void addIndex(int index,int data) {
        // 一定注意边界条件
        // 判断index的合法性
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        // 若index = 0;
        if (index == 0) {
            // 链表的头部节点插入
            addFirst(data);
            return;
        }
        // 说明此时index合法且在中间位置(包含最后节点)
        // 此时需要找到待插入位置index的前驱节点
        // 单链表中只能从前到后遍历
        Node node = new Node(data);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // prev引用指向当前插入index的前驱
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    public void addLast(int data) {
        addIndex(size,data);
    }

    /**
     * 查询index位置的节点数据
     * @param index
     * @return 节点数据
     */
    public int get(int index) {
        if (rangeCheck(index)) {
            Node node = head;
            for (int i = 0;i < index;i++) {
                node = node.next;
            }
            // 此时node指向待查找元素的索引
            int data = node.data;
            return data;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    /**
     * 修改单链表中index位置的元素
     * 返回修改前的元素值
     * @param index
     * @param data
     * @return
     */
    public int set(int index,int data) {
        if (rangeCheck(index)) {
            // 需要找到index位置的节点
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            int oldData = node.data;
            node.data = data;
            return oldData;
        }else {
            System.err.println("set index illegal!");
            return -1;
        }
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    /**
     * 判断单链表中是否包含元素data
     * @param data
     * @return
     */
    public boolean contains(int data) {
        Node node = head;
        while (node != null) {
            if (node.data == data) {
                System.out.println("找到元素！");
                return true;
            }
            node = node.next;
        }
        System.out.println("没有找到该元素");
        return false;
    }

    public void removeFirst() {
        Node node = head;
        head = head.next;
        node.next = null;
        size --;
    }

    public void removeIndex(int index) {
        // 判断边界条件
        if (rangeCheck(index)) {
            if (index == 0) {
                // 此时删除头节点
                removeFirst();
            }else {
                // 此时index删除的中间位置节点
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                // prev指向待删除节点的前驱节点
                // node就是待删除的节点
                Node node = prev.next;
                // 链接前驱节点和后继节点
                prev.next = node.next;
                // 将当前节点的next引用置为空，脱钩操作
                node.next = null;
                size --;
            }
        }else {
            System.err.println("remove index illegal!");
        }
    }

    /**
     * 删除链表中指定元素的第一个节点
     * @param data
     */
    public void removeValueOnce(int data) {
        // 先要找到待删除的元素的节点
        // 先判断头节点的情况
        if (head.data == data) {
            // 此时头节点就是第一个待删除的节点
            removeFirst();
        }else {
            // 此时头节点一定不是要删除的节点
            // 从头节点开始找到待删除的节点前驱
            Node prev = head;
            // 此时要看下一个节点的情况
            while (prev.next != null) {
                // 找到待删除的节点
                if (prev.next.data == data) {
                    // 此时perv就是待删除节点的前驱
                    // node节点就是待删除的节点
                    Node node = prev.next;
                    // 将prev跳过当前node
                    prev.next = node.next;
                    node.next = null;
                    size --;
                    break;
                }else {
                    // 此时prev的下一个节点不是待删除的节点
                    // 继续向下一个节点前进
                    prev = prev.next;
                }
            }
        }
    }

    public void removeAllValue(int data) {
        // 判断头节点的情况
        // 头节点以及之后出现了多个连续待删除的节点
        while (head != null && head.data == data) {
            Node node = head;
            head = head.next;
            node.next = null;
            size --;
        }
        // 此时head一定不是待删除的节点
        // head.data != data
        if (head == null) {
            // 此时链表全部是待删除的节点，全部删除完毕
            return;
        }else {
            // 此时头节点已经处理完毕，并且链表也不为空，向下一个节点开始判断
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.data == data) {
                    // node就是待删除的节点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size --;
                }else {
                    // 此时prev的下一个节点不是要删除的节点，prev继续向后走一个单位
                    prev = prev.next;
                }
            }
        }
    }


    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(2);
        System.out.println(singleLinkedList);
        singleLinkedList.removeAllValue(2);
        // 3
        System.out.println(singleLinkedList);
    }

    @Override
    public String toString() {
        String ret = "";
        // 为啥此时要有一个临时变量node来存储head的值?
        Node node = head;
        while (node != null) {
            ret += node.data + "->";
            // 继续访问下一节车厢
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}
